#include <iostream>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <list>
#include <map>

#include "Listnode.h"
#include "Network.h"
#include "descriptor.h"


#define LEFT 1
#define UP 2
#define DIAG 0

using namespace std;

//Comparison function for the hash map
/*class compareKey
{
	public:
		bool operator()(const vector<int> &Key1 , const vector<int> &Key2)
		{
			if(Key1.size() == Key2.size())
			{
				
			}
			else
			{
				return false;
			}
		}
};*/


/*vector<int> LCS (vector<int> &x , vector<int> &y)
{
	//Print out the vectors x and y
	vector<int>::iterator it;
	cout << "Vector X\n";
	for(it = x.begin() ; it < x.end() ; it++)
	{
		cout << *it << "  ";
	}
	cout << "\n";
	cout << "Vector Y\n";
	for(it = y.begin() ; it < y.end() ; it++)
	{
		cout << *it << "  ";
	}
	cout << "\n";
	int m = x.size() + 1;
	int n = y.size() + 1;
	vector<int> temp;
	vector<int> z; //output vector
	
	//Create the cost table of size (m+1)x(n+1)
	int **c = new int* [m];
	int **b = new int* [m];
	for(int i = 0 ; i < m ; i++)
	{
		c[i] = new int [n];
		b[i] = new int [n];
	}
	
	//Initialize the cost table
	for(int i = 0 ; i < m ; i++)
	{
		c[i][0] = 0;
	}
	for(int j = 1; j < n ; j++)
	{
		c[0][j] = 0;
	}
	
	//Start the dynamic programming step
	for(int i = 1 ; i < m ; i++)
	{
		for(int j = 1 ; j < n ; j++)
		{
			//This is the case where the last element of the prefix of 'x' is equal
			//to the prefix of 'y'
			if(x[i-1] == y[j-1])
			{
				c[i][j] = c[i-1][j-1] + 1;
				b[i][j] = DIAG;
				
			}
			
			else
			{
				if(c[i-1][j] >= c[i][j-1])
				{
					c[i][j] = c[i-1][j];
					b[i][j] = UP;
				}
				else
				{
					c[i][j] = c[i][j-1];
					b[i][j] = LEFT;
				}
			}
		}
	}
	
	//Print out matrix B
	cout << "B\n";
	for(int i = 0; i < m ;i++)
	{
		for(int j = 0; j < m ; j++)
		{
			cout << b[i][j]<<" ";
		}
		cout<<"\n";
	}
	//Build the vector z
	
	int i = m-1;
	int j = n-1;
	
	while(i > 0 && j > 0)
	{
	
		if(b[i][j] == UP)
		{
			i--;
		}
		else if (b[i][j] == LEFT)
		{
			j--;
		}
		else if (b[i][j] ==DIAG)
		{	
			temp.push_back(x[i-1]);
			i--;
			j--;
		}
	}
	
	if(temp.size() != 0)
	{
		for(it = --temp.end() ;it >= temp.begin(); it--)
		{
			z.push_back(*it);
		}
	} 
	
	//print out the vector z
	cout << "Vector Z\n";
	for(it = z.begin() ; it < z.end() ; it++)
	{
		cout << *it << "  ";
	}
	cout << "\n";
	
	return z;
}*/


vector<int> LCS(vector<int> x, vector<int> y)
{
	vector<int>::iterator itx = x.begin();
	vector<int>::iterator ity = y.begin();
	vector<int> z;
	while(itx!=x.end() && ity!=y.end())
	{
		if( *itx < *ity)
		{
			itx ++ ;
		}
		else if (*itx > *ity)
		{
			ity++;
		}
		else
		{
			z.push_back((*itx));
			itx++;
			ity++;
		}
	}
		
	return z;
}




//This function tests whether a given PSE is subsumed or not
bool Subsumed(Listnode &G, map< vector<int>,vector<Descriptor> > &H , int sig, int period)
{
	bool subsumed = false;
	
	/*//Get the details of the listnode like graph, start and end
	vector<int> graph = G.get_graph();//the graph in the listnode
	int start = G.get_start();//the start index of the PSE
	int end = G.get_end();//the end index of the PSE 
	int support = G.get_support();//the support of the PSE
	
	//Get an iterator to the map
	map< vector<int> , vector<Descriptor> >::iterator Mit;
	
	Mit = H.find(graph);
	
	//Check if the graph is present in the hash map. If it is not, then check
	//if it is frequent enough. If it is, then add it to the hash map
	if(Mit == H.end())
	{
		if(support >= sig)
		{
			if( (start - (start%100)) == 200)
			{
				cout << "\nGraph"<<endl;
				for(vector<int>::iterator it = graph.begin() ; it < graph.end() ; it++)
				{
					cout << *it <<"\t";
				}
				cout << "\n";
				cout << "Start " <<start << endl;
				cout << "End " <<end << endl;
				cout << "Support " <<support << endl;
				cout << "Period " << period << endl;
				cout <<"is not found and is being added\n";
			}
			Descriptor d;
			d.start = start;
			d.end = end;
			d.support = support;
			d.period = period;
			
			//Create a vector of descriptors which you'll push in with the graph
			vector<Descriptor> L;
			L.push_back(d);
			H.insert(pair<vector<int>,vector<Descriptor> >(graph,L));
		}
	}
	
	else
	{

		vector<Descriptor> list_of_descriptors = (*Mit).second;
	
		//Now cycle through each of the descriptors in the list
		vector<Descriptor>::iterator lt;
		
		for(lt = list_of_descriptors.begin() ; lt < list_of_descriptors.end() ; lt++)
		{
			if(period % (*lt).period == 0 && start >= (*lt).start && end <= (*lt).end && support >= sig)
			{
				//Print out graph
				if( (start - (start%100)) == 200)
				{
					cout << "\nGraph"<<endl;
					for(vector<int>::iterator it = graph.begin() ; it < graph.end() ; it++)
					{
						cout << *it <<"\t";
					}
					cout<<"\n";
					cout << "Start " <<start << endl;
					cout << "End " <<end << endl;
					cout << "Support " <<support << endl;
					cout << "Period " << period << endl;
					cout <<"is subsumed\n";
				}
				subsumed = true;
				break;
			}
		}
	
		if(subsumed == false && support >= sig)
		{
			if( (start - (start%100)) == 200)
			{
				cout << "\nGraph"<<endl;
				for(vector<int>::iterator it = graph.begin() ; it < graph.end() ; it++)
				{
					cout << *it <<"\t";
				}
				cout << "\n";
				cout << "Start " <<start << endl;
				cout << "End " <<end << endl;
				cout << "Support " <<support << endl;
				cout << "Period " << period << endl;
				cout <<"is not subsumed and is being added\n";
			}
			Descriptor d;
			d.start = start;
			d.end = end;
			d.support = support;
			d.period = period;
			
			// Push this descriptors in the list of descriptors for the graph
			
			list_of_descriptors = (*Mit).second;
			list_of_descriptors.push_back(d);
		}	
		
	}*/
	return subsumed;
}

void update_output(map<string, int> &Output , int time , int support)
{
	//create the checkpoint;
	int checkpoint = time - (time % 100);
	/*cout << "time = " << time << endl;
	cout << "checkoint = " << checkpoint << endl;*/
	//Check if the checkpoint-support pair exists
	stringstream ss;
	ss << checkpoint <<"-"<<support;
	map<string,int>::iterator it;
	it = Output.find(ss.str());
	
	if(it == Output.end()) //This particular checkpoint-support pair doesn't exist
	{
		Output.insert(pair<string,int>(ss.str(),1));
	}
	else
	{
		//This means that the checkpoint-support pair has been found
		(*it).second = (*it).second + 1;	
	}
	return;
}

void update(list<Listnode> &L, int t, map< vector<int>,vector<Descriptor> > &H , int sig, int period , map<string,int> &Output)
{
	//Get the graph Gt
	vector<int> Gt;
	Listnode first_node = L.front();
	Gt = first_node.get_graph();

	//Set the iterator to the next node in the list
	list<Listnode>::iterator N;
	N = L.begin();
	N ++;
	
	//If newly added graph is empty
	/*if(Gt.size() == 0)
	{
		while (N != L.end())
		{
			if( ((*N).get_graph()).size() != 0 && !Subsumed((*N),H,sig,period) && (*N).get_support() >= sig)
			{
				update_output(Output,(*N).get_start() , (*N).get_support());
			}
			N = L.erase(N);
		}
		L.clear();
	}*/
	
	//Start the loop from the second element of the list
	while(N!= L.end())
	{
		vector<int> F;
		vector<int> C;
		
		//(*N).print_listnode();
		F = (*N).get_graph();//current node graph
		int s = (*N).get_support();
		C = LCS(F,Gt); //Intersection of the current Gt and the current node graph
		
		/*if(F == Gt)	 
		{
			//Delete the first node
			N = L.erase(L.begin());
			for(N = L.begin() ; N != L.end() ; N++)
			{
				(*N).update_end_index(t);
				(*N).update_support((*N).get_support()+1);
			}
			
		}*/
		
		 if(C==F /*&& F!= Gt*/)
		{
			while(N != L.end())
			{
				(*N).update_end_index(t); //The end index of N is set to t
				(*N).update_support((*N).get_support()+1);
		
				vector<int> curr_graph = (*N).get_graph();
				N--;
				vector<int> prev_graph = (*N).get_graph();
				
				if(curr_graph == prev_graph)
				{
					N = L.erase(N);
				}
				else
				{
					N++;
				}
				
				N++;
			}
		}
		
		else if(C.size() == 0)
		{
			while(N != L.end())
			{
				s = (*N).get_support();
				if( ((*N).get_graph()).size() != 0 && !Subsumed((*N),H,sig,period) && (*N).get_support() >= sig)
				{
					update_output(Output,(*N).get_start() , (*N).get_support());
				}
				N = L.erase(N);
			}
		}
		
		else
		{
			if( ((*N).get_graph()).size() != 0 && !Subsumed((*N),H,sig,period) && (*N).get_support() >= sig)
			{
				update_output(Output,(*N).get_start() , (*N).get_support());
			}
			(*N).update_graph(C);
			(*N).update_end_index(t); //update the end index
			(*N).update_support((*N).get_support()+1);
	
			vector<int> curr_graph;
			vector<int> prev_graph;
			curr_graph = (*N).get_graph();
			N--;
			prev_graph = (*N).get_graph();
	
			if(curr_graph == prev_graph)
			{
				N = L.erase(N);
			}
			else
			{
				N++;
			}
	
			N++;
			
		}
	}
}


int main(int argc, char* argv[])
{
	
	//Read in the Network
	Network dyn;
	dyn.read_network("data/enron-small");
	//dyn.print();
	
	//Subgraph hash map
	map <vector<int> , vector<Descriptor> > H;
	
	//Output hash map
	map <string , int> Output;
	
	//Loop through the timesteps
	int T = dyn.get_epoch();
	vector<int> G;

	//Create the bidimensional array A
	int Pmax = 10;
	int sig =3;
	list<Listnode> ***A;
	A = new list<Listnode>** [Pmax + 1];
	if(A ==NULL)
		{
			cout << "Memory allocation error!\n";
			exit(0);
		}
	for(int p = 1 ; p<=Pmax ; p++)
	{
		A[p] = new list<Listnode>* [p];
		if(A[p] ==NULL)
		{
			cout << "Memory allocation error!\n";
			exit(0);
		}
		for(int m = 0 ; m < p ; m++)
		{
			A[p][m] = new list<Listnode>;
			if(A[p][m] ==NULL)
			{
			cout << "Memory allocation error!\n";
			exit(0);
			}
		}
		
	}

	cout << "Total number of timesteps = " << T <<endl;
	for(int t = 0 ; t < T ; t++)
	{
		G = dyn.get_timestep();
		//cout << "\nt = " << t << endl;
		for(int p = 1 ; p <=Pmax; p++)
		{
			int m = t%p;
			Listnode new_node(G,t,t,1);
			(*(A[p][m])).push_front(new_node);
			update(*A[p][m],t,H,sig,p,Output);
		}
	}
	//Update the output in the bidimensional array
	for(int p = 1; p < Pmax ; p++)
	{
		for(int m = 0; m < p ; m++)
		{
			list<Listnode>::iterator it;
			for(it = (*A[p][m]).begin(); it != (*A[p][m]).end() ; it++)
			{
				if( ((*it).get_graph()).size() != 0 && !Subsumed((*it),H,sig,p) && (*it).get_support() >= sig)
				{
					//(*it).print_listnode();
					update_output(Output,(*it).get_start() , (*it).get_support());
				}
			}
		}
	}
	
	//Print the output
	map<string,int>::iterator Ot;
	for(Ot = Output.begin() ; Ot != Output.end() ; Ot++)
	{
		cout << (*Ot).first << "="<<(*Ot).second<<endl;
	}

	return 0;
}

